package dfs_bfs;

import java.util.LinkedList;
import java.util.Queue;

public class ls130 {
    public static void main(String[] args) {
        solve_bfs(new char[][]{{'X','X','X','X'},{'X','O','O','X'},
                {'X','X','O','X'},{'X','O','X','X'}});
    }

    public static void solve_bfs(char[][] board) {
        int m = board.length, n = board[0].length;
        Queue <int []> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            if(board[i][0] == 'O')
                queue.add(new int[]{i, 0});
            if(board[i][n - 1] == 'O')
                queue.add(new int[]{i, n - 1});
        }
        for (int i = 0; i < board[0].length; i++) {
            if(board[0][i] == 'O')
                queue.add(new int[]{0, i});
            if(board[m - 1][i] == 'O')
                queue.add(new int[]{m - 1, i});
        }
        while( !queue.isEmpty()){
            int[] temp = queue.poll();
            int i = temp[0], j = temp[1];
            if(i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'O'){
                board[i][j] = 'Y';
                queue.add(new int[]{i + 1, j});
                queue.add(new int[]{i - 1, j});
                queue.add(new int[]{i, j + 1});
                queue.add(new int[]{i, j - 1});
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                if(board[i][j] == 'Y')
                    board[i][j] = 'O';
            }
        }
    }

    public static void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, board[0].length - 1);
        }
        for (int i = 0; i < board[0].length; i++) {
            dfs(board, 0, i);
            dfs(board, board.length - 1, i);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                if(board[i][j] == 'Y')
                    board[i][j] = 'O';
            }
        }
    }
    public static void dfs(char[][] board, int i, int j){
        if(i >= board.length || i < 0 || j >= board[0].length ||j < 0 || board[i][j] == 'X' || board[i][j] == 'Y')
            return;
        board[i][j] = 'Y';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}
